class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int n = arr.size();
        vector<int> pre = arr;
        for(int i = 1; i < n; i++){
            pre[i] += pre[i - 1];
        }
        int ans = 0;
        for(int len = 1; len <= n; len += 2){ // 枚举长度
            for(int s = 0; s + len <= n; s++){ // 枚举起点
                ans += pre[s + len - 1] - pre[s] + arr[s];
            }
        }
        return ans;
    }
};

/**
 * 2021.8.29
 * 前缀和可以优化到 O(n ^ 2)
 * 数学方法可以优化到 O(n)
 * 但是临场想出数学方法太难
 * 还是精进这种通用的方法比较合适
 */